
\subsection{Problem 3 (11)}

Recommended, 11 Points: Next, implement a WCET-oriented solution for the given problem, which has a good worst-case performance, automatically analyzable control flow, and, assuming a suitable processor, a small execution time variance. To this end, it is acceptable to add additional parameters to functions, and to use different algorithms. Again, perform measurements and a WCET analysis, and summarize all collected results in a table in your report.
\\
\\
\textbf{Solution:}
\\
\\
One can find the source code for the WCET oriented solution in Section~\ref{sec:source_v3} and Section~\ref{sec:header_v3}. We managed to optimize the single path version only marginal. 
\\
\\
While inspecting the source code we recognized, that the first two points of the lower hull are static assignments. So we moved this code section in front of the loop. Also, the first point of the upper hull is static too. So we moved this assignment in front of the second loop.
\\
We thought of another advantage: The multiplication statement ``cross'' only has to be executed when the variable ``res\_k'' has the value 1. But the variable ``res\_k'' is input data dependent because it is dependent on the variable ``k''. So we are not allowed to evaluate this in an appropriate ``if''statement. This would be not a correct single path version any more. But we tried this advantage and we observed a huge speedup.
\\
\\
In Figure~\ref{fig:v3_ait} one can find the WCET analysis of the optimized version. In the Table below one can find a comparison of the three source code versions. 

\begin{figure}[!htbp]
	\centering
		\includegraphics[width=0.50\textwidth]{figures/v3_ait.png}
	\caption{aiT analysis v3}
	\label{fig:v3_ait}
\end{figure}

\begin{table}[!htbp]
\centering
	\begin{tabular}[!htpb]{|c|c|c|} 
		\hline
			& Measurement & aiT \\
		\hline
		\hline
		convex v1 & 5939 & 57788 \\
		convex v2 & 66795 & 142364 \\
		convex v3 & 62051 & 132444 \\
		\hline
	\end{tabular} 
	\caption{Results of Measurement and aiT analysis}
\end{table} 

\noindent So we managed to optimize the code only by a small amount of time.